public class MinAddToMakePalindrome {

    // KMP 前缀函数，计算最长前缀后缀匹配的长度
    public static int[] computePrefix(String str) {
        int n = str.length();
        int[] prefix = new int[n];
        int j = 0;  // j是当前匹配的长度

        for (int i = 1; i < n; i++) {
            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = prefix[j - 1];  // 如果不匹配，回溯
            }
            if (str.charAt(i) == str.charAt(j)) {
                j++;
            }
            prefix[i] = j;
        }

        return prefix;
    }

    // 主函数：返回添加最少字符使其成为回文串
    public static int minAddToMakePalindrome(String s) {
        // 构造新字符串 "s + '#' + reversed(s)"
        String reversed = new StringBuilder(s).reverse().toString();
        String combined = s + "#" + reversed;

        // 计算前缀数组
        int[] prefix = computePrefix(combined);

        // 最小需要添加的字符数 = s.length() - prefix[combined.length() - 1]
        int matchLength = prefix[combined.length() - 1];
        return s.length() - matchLength;
    }

    public static void main(String[] args) {
        String s = "aacecaaa";
        System.out.println(minAddToMakePalindrome(s));  // 输出 2

        s = "abcd";
        System.out.println(minAddToMakePalindrome(s));  // 输出 4
    }
}